import LinkedList, {equalsType} from "../LinkedList"
import defaultEquals from "../../utils/defaultEquals";
import DoublyNode from "./DoublyNode";
// 双向列表数据结构
export default class DoubleLinkedList<T> extends LinkedList<T> {
    tail?: DoublyNode<T>; // 保存最后一个插入的元素
    constructor(equalsFn: equalsType<T> = defaultEquals) {
        super(equalsFn);
        this.tail = undefined;
    }

    insert(element: T, index: number) {
        let new_node: DoublyNode<T> = new DoublyNode();
        new_node.value = element;
        if (index < 0 || index > this.count) {
            throw new Error("下标越界")
        }
        this.count++;
        let p_node: DoublyNode<T> | undefined = undefined;
        let n_node: DoublyNode<T> | undefined = undefined;

        if (index === 0) {
            new_node.next = this.head;
            // 如果没有head为空 则说明列表是空的
            if(!this.head){
                this.tail = new_node
            }
            this.head = new_node;
            return;
        }
        // 获取上一个元素
        p_node = <DoublyNode<T>>this.getElementAt(index - 1);
        // 获取下一个元素(下一个元素可能是undefined)
        n_node = p_node.next;
        // 上一个元素的next指向新增元素
        p_node.next = new_node;
        // 新增元素的prev指向上一个元素
        new_node.prev = p_node;

        // 新增元素的next指向下一个元素
        new_node.next = n_node;
        // 如果下一个元素存在则让下一个元素的prev指向本元素
        if (n_node) {
            n_node.prev = new_node;
        }else{
            // 如果不存在说明已经到了末尾, 将末尾指针指向当前元素
            this.tail = new_node
        }
    }

    removeAt(index: number): T | undefined {
        if (this.isEmpty() || index >= this.count || index < 0) {
            return undefined;
        }

        let now_node = <DoublyNode<T>>this.getElementAt(index);
        let p_node = <DoublyNode<T>>this.getElementAt(index - 1);
        let n_node = now_node.next
        if (index === 0) {
            this.head = n_node;
        }
        if (p_node) {
            p_node.next = n_node;
        }
        if (n_node) {
            n_node.prev = p_node;
        }else{
            // 如果没有下一个 说明删掉的是末尾
            this.tail = p_node
        }
        // 如果count为1 说明链表要被清空了
        if(this.count === 1){
            this.tail = undefined;
        }
        this.count--;
        return now_node?.value;
    }
}
